package leetcode.hot100;

import pojo.ListNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 23. 合并 K 个升序链表
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 *
 * @author: yjf
 * @date: 2024/12/4
 */
public class LeetCode23 {

    // 分值法(把对应链表拆分成两两比较大小合并)
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    public static ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        int mid = l + (r - l) / 2;
        return mergeKLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public static ListNode mergeKLists(ListNode node1, ListNode node2) {
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                tail.next = node1;
                node1 = node1.next;
            } else {
                tail.next = node2;
                node2 = node2.next;
            }
            tail = tail.next;
        }
        tail.next = node1 == null ? node2 : node1;
        return head.next;
    }

    public static void main(String[] args) {
        // 输入：lists = [[1,4,5],[1,3,4],[2,6]]
        ListNode node1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode node2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode node3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = new ListNode[]{node1, node2, node3};
        ListNode result = mergeKLists(lists);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }
}
